package leetcode.code0085;

/**
 *
 * 执行用时：3 ms, 在所有 Java 提交中击败了99.98%的用户
 *
 * 内存消耗：41.7 MB, 在所有 Java 提交中击败了25.25%的用户
 *
 * 通过测试用例：71 / 71
 *
 * @author CaoYu
 * @date 2021年11月26日
 * @description
 */
public class Solution2 extends Solution85 {

	@Override
	public int maximalRectangle(char[][] matrix) {
		if (matrix == null) {
			return 0;
		}
		int rowSize = matrix.length;
		if (rowSize == 0) {
			return 0;
		}
		int colSize = matrix[0].length;
		if (colSize == 0) {
			return 0;
		}
		int[] line = new int[colSize];
		int max = 0;
		for (int i = 0; i < rowSize; i++) {
			for (int j = 0; j < colSize; j++) {
				line[j] += matrix[i][j] == '0' ? -line[j] : matrix[i][j] - '0';
			}
			max = Math.max(max, this.f(line, colSize));
		}
		return max;
	}

	private int f(int[] line, int colSize) {
		int ans = 0;
		int[] s = new int[colSize];
		int p = -1;
		for (int i = 0; i < colSize; i++) {
			if (p > -1 && line[s[p]] >= line[i]) {
				int right = s[p];
				do {
					int index = s[p--];
					int left = p == -1 ? -1 : s[p];
					ans = Math.max(ans, (right - left) * line[index]);
				} while (p > -1 && line[s[p]] >= line[i]);
			}
			s[++p] = i;
		}
		int right = p > -1 ? s[p] : 0;
		while (p > -1) {
			int index = s[p--];
			int left = p == -1 ? -1 : s[p];
			ans = Math.max(ans, (right - left) * line[index]);
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
